//
// Created by TianBo on 2022/6/3.
//

//自定义排序规则，如果 A + B > B + A 则 A > B 此时需要将B排在A前面(因为求最小)
// 改写快排

#include "iostream"
#include "vector"
#include "string"

using namespace std;

class Solution {
public:
    string minNumber(vector<int>& nums) {
        vector<string> numstr(nums.size());
        for (int i = 0; i < nums.size(); ++i) {
            numstr[i] = to_string(nums[i]);
        }
        quickSort(numstr,0,numstr.size());
        string res = "";
        for(auto s : numstr)
            res += s;
        return res;
    }

    void quickSort(vector<string>& strs,int left,int right) {
        if(left >= right)
            return;
        int i = left,j = right;
        while (i < j)
        {
            while (strs[j] + strs[left] >= strs[left] + strs[j] && i < j) j--;
            while (strs[i] + strs[left] <= strs[left] + strs[i] && i < j) i++;
            swap(strs[i],strs[j]);
        }
        swap(strs[left],strs[i]);
        quickSort(strs,left,i-1);
        quickSort(strs,i+1,right);
    }
};

int main()
{

}